1. Field of the Invention
This application relates generally to computer systems in which a host is configured to present each of multiple contexts provided to run on the host with an address space that may from time to time be mapped, at least in part, to a corresponding one or more portions of a host memory, and, more specifically, to methods for supporting memory management decisions in such a system.
2. Description of Related Art
In the computer system 100 illustrated in FIG. 1, multiple contexts 102a, 102b, 102c execute concurrently on a host 104 and share some or all of a host memory 106. Because the host memory 106 is usually not large enough to hold the address spaces of all of the contexts at the same time, the contexts usually compete for use of the host memory 106. A memory manager 108 executing on the host 104 is typically provided to resolve these competing requests by deciding which portions, if any, of the address spaces of the contexts 102a, 102b, 102c can be stored in the host memory 106 at a particular time. The system typically includes secondary storage 110, such as a disk or other usually non-volatile mass-storage device, for holding those portions of the address spaces for each of the contexts 102a, 102b, 102c that cannot be accommodated in the host memory 106 at a given time.
The memory manager 108 may attempt to alleviate contention for the host memory 106 by identifying portions of the address spaces of one or more of the contexts that contain identical data, and then mapping those portions to the same portion of the host memory. Examples of such an approach are described in U.S. Pat. Nos. 6,789,156 (“Content-based, transparent sharing of memory units,” issued 7 Sep. 2004), and 6,075,938, (“Virtual machine monitors for scalable multiprocessors,” issued 13 June 2000), both of which are hereby fully incorporated by reference herein as though set forth in full. Such an approach is beneficial because it tends to allow the host to keep a greater number of contexts resident in memory, and also tends to allow for more efficient operation by necessitating fewer instances of swapping, that is, transferring portions of the contents of the memory to secondary storage (usually, the disk) so as to make room for disk content to be transferred into the thus freed-up memory space. This is typically done because it is usually much faster to access data, code, etc., stored in memory than to have to access the swapped data, code, etc., from secondary storage.
Consider the example shown in FIG. 2, which illustrates the address spaces 112a, 112b, 112c of the contexts 102a, 102b, 102c, respectively, in the computer system of FIG. 1 at a particular time. In this particular example, memory manager 108 is configured to map identical portions of the same or different address spaces to the same portion of the host memory 106. As illustrated, portions 114, 116 and 126 of the address spaces 112a and 112b are identical and therefore mapped to the same portion 120 of the host memory 106 through mapping tables 122a and 122b, respectively. Compared to the case where the portions 114, 116 and 126 are mapped to different portions of the host memory (as shown in phantom), the approach of mapping these portions to the same portion 120 of the host memory 106 frees up the portions 124 and 128 for use by another context.
Turning back to FIG. 1, the memory manager 108 is responsible for making memory management decisions in the system from time to time, including decisions such as whether and how much of the host memory 106 to allocate to a particular context, and whether and how much of the host memory 106 to reclaim from a particular context.
To support or optimize these decisions, the memory manager 108 may utilize selected information about the contexts such as, for example, the amount of host memory 106 in active use by a particular context. However, due to the dynamically changing nature of the system, this information may become inaccurate and outdated, rendering it unfit for use by the memory manager 108. Moreover, timely updates of this information are often not possible given the time that may be required to gather this information. Also, certain approximations of this information that have been proposed for use by the memory manager 108 sacrifice an inordinate amount of accuracy for ease and speed of computation, and therefore lend themselves to sub-optimal memory management decisions.
The problem is compounded when the memory manager 108 is configured to map identical portions of address spaces of the same or different contexts to the same portion of the host memory 106. In this case, the amount of host memory 106 allocated to a context will often overstate the true amount of host memory 106 properly allocable to the context. Moreover, an accurate estimate of the amount of host memory properly allocable to a context has proven difficult to compute in real time, and proposed approximations of this statistic are too inaccurate to support reliable memory management decisions.
Additionally, the use of back mapping (also known as reverse mapping), which is mapping from a portion of physical memory back to any corresponding portions of virtual memory, to obtain more accurate computations has not proven feasible because back maps are expensive to implement, consume excessive host resources and spatial overhead, and cannot be easily maintained as fixed-size data structures. In FIG. 2, for example, back mapping would require storing three back map pointers, from portion 120 of host memory 106 back to portions 114 and 126 in address space 112a, and portion 116 in address space 112b. The disadvantages of back mapping become even more severe when the degree of memory-sharing is high. Consider, for example, that in a system where thousands of virtual pages are all mapped to a single, physical page, back mapping would require the storage of corresponding thousands of back map pointers.